package com.glb.leetcode;

import java.util.Arrays;

// https://leetcode.cn/problems/merge-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150
public class C1_ArrayCombine {

  public static void main(String[] args) {
    // int nums1[] = {1,2,3,0,0,0}, nums2[] = {2,5,6};
    // int m = 3, n = 3;

    int nums1[] = {1}, nums2[] = {};
    int m = 1, n = 0;

    // int nums1[] = { 0 }, nums2[] = { 1 };
    // int m = 0, n = 1;

    merge(nums1, m, nums2, n);

    System.out.println(Arrays.toString(nums1));
  }

  // public static void merge(int[] nums1, int m, int[] nums2, int n) {
  // for (int i = 0; i < n; i++) {
  // nums1[m + i] = nums2[i];
  // }
  // Arrays.sort(nums1);
  // // for (int i = 0; i < nums1.length; i++) {
  // // for (int j = i + 1; j < nums1.length; j++) {
  // // if (nums1[i] > nums1[j]) {
  // // int temp = nums1[i];
  // // nums1[i] = nums1[j];
  // // nums1[j] = temp;
  // // }
  // // }
  // // }
  // }

  // public static void merge(int[] nums1, int m, int[] nums2, int n) {
  // int p1 = 0, p2 = 0;
  // int[] sorted = new int[m + n];
  // int cur;
  // while (p1 < m || p2 < n) {
  // if (p1 == m) {
  // cur = nums2[p2++];
  // } else if (p2 == n) {
  // cur = nums1[p1++];
  // } else if (nums1[p1] < nums2[p2]) {
  // cur = nums1[p1++];
  // } else {
  // cur = nums2[p2++];
  // }
  // sorted[p1 + p2 - 1] = cur;
  // }
  // for (int i = 0; i != m + n; ++i) {
  // nums1[i] = sorted[i];
  // }
  // }

  public static void merge(int[] nums1, int m, int[] nums2, int n) {
    int p1 = m - 1, p2 = n - 1;
    int tail = m + n - 1;
    int cur;
    while (p1 >= 0 || p2 >= 0) {
      if (p1 == -1) { // nums1 的数据已经遍历完
        cur = nums2[p2--];
      } else if (p2 == -1) {  // nums2 的数据已经遍历完
        cur = nums1[p1--];
      } else if (nums1[p1] > nums2[p2]) {
        cur = nums1[p1--];
      } else {
        cur = nums2[p2--];
      }
      nums1[tail--] = cur;
    }
  }

}
